Search Results

Documents authored by Cacchiani, Valentina

Document
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2019
OASIcs, Volume 75, ATMOS'19, Complete Volume

Authors: Valentina Cacchiani and Alberto Marchetti-Spaccamela

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract
OASIcs, Volume 75, ATMOS'19, Complete Volume
Cite as

19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Proceedings{cacchiani_et_al:OASIcs.ATMOS.2019,
  title =	{{OASIcs, Volume 75, ATMOS'19, Complete Volume}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019},
  URN =		{urn:nbn:de:0030-drops-114516},
  doi =		{10.4230/OASIcs.ATMOS.2019},
  annote =	{Keywords: Theory of computation, Design and analysis of algorithms; Mathematics of computing, Discrete mathematics; Combinatorics; Mathematical optimization;}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2019.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Valentina Cacchiani and Alberto Marchetti-Spaccamela

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cacchiani_et_al:OASIcs.ATMOS.2019.0,
  author =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{0:i--0:x},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.0},
  URN =		{urn:nbn:de:0030-drops-114123},
  doi =		{10.4230/OASIcs.ATMOS.2019.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2012.1
A Fast Heuristic Algorithm for the Train Unit Assignment Problem

Authors: Valentina Cacchiani, Alberto Caprara, and Paolo Toth

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
In this paper we study a railway optimization problem known as the Train Unit Assignment Problem. A train unit consists of a self-contained train with an engine and a set of wagons with passenger seats. Given a set of timetabled train trips, each with a required number of passenger seats, and a set of train units, each with a given number of available seats, the problem calls for the best assignment of the train units to the trips, possibly combining more than one train unit for a given trip, that fulfills the seat requests. We propose a heuristic algorithm based on the computation of a lower bound obtained by solving an Integer Linear Programming model that gives the optimal solution in a "peak period" of the day. The performance of the heuristic algorithm is computationally evaluated on real-world instances provided by a regional Italian Train Operator. The results are compared with those of existing methods from the literature, showing that the new method is able to obtain solutions of good quality in much shorter computing times.
Cite as

Valentina Cacchiani, Alberto Caprara, and Paolo Toth. A Fast Heuristic Algorithm for the Train Unit Assignment Problem. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{cacchiani_et_al:OASIcs.ATMOS.2012.1,
  author =	{Cacchiani, Valentina and Caprara, Alberto and Toth, Paolo},
  title =	{{A Fast Heuristic Algorithm for the Train Unit Assignment Problem}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{1--9},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.1},
  URN =		{urn:nbn:de:0030-drops-36971},
  doi =		{10.4230/OASIcs.ATMOS.2012.1},
  annote =	{Keywords: Train Unit Assignment, Heuristic Algorithm, ILP model, Real-world instances}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2008.1590
Recoverable Robustness for Railway Rolling Stock Planning

Authors: Valentina Cacchiani, Alberto Caprara, Laura Galli, Leo Kroon, and Gábor Maróti

Published in: OASIcs, Volume 9, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) (2008)

Abstract
In this paper we explore the possibility of applying the notions of Recoverable Robustness and Price of Recoverability (introduced by [5]) to railway rolling stock planning, being interested in recoverability measures that can be computed in practice, thereby evaluating the robustness of rolling stock schedules. In order to lower bound the Price of Recoverability for any set of recovery algorithms, we consider an "optimal" recovery algorithm and propose a Benders decomposition approach to assess the Price of Recoverability for this "optimal" algorithm. We evaluate the approach on real-life rolling stock planning problems of NS, the main operator of passenger trains in the Netherlands. The preliminary results show that, thanks to Benders decomposition, our lower bound can be computed within relatively short time for our case study.
Cite as

Valentina Cacchiani, Alberto Caprara, Laura Galli, Leo Kroon, and Gábor Maróti. Recoverable Robustness for Railway Rolling Stock Planning. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{cacchiani_et_al:OASIcs.ATMOS.2008.1590,
  author =	{Cacchiani, Valentina and Caprara, Alberto and Galli, Laura and Kroon, Leo and Mar\'{o}ti, G\'{a}bor},
  title =	{{Recoverable Robustness for Railway Rolling Stock Planning}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{1--13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-07-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{9},
  editor =	{Fischetti, Matteo and Widmayer, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2008.1590},
  URN =		{urn:nbn:de:0030-drops-15902},
  doi =		{10.4230/OASIcs.ATMOS.2008.1590},
  annote =	{Keywords: Recoverable robustness, Railway rolling stock scheduling, Benders decomposition}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2007.1172
06. Solving a Real-World Train Unit Assignment Problem

Authors: Valentina Cacchiani, Alberto Caprara, and Paolo Toth

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)

Abstract
INVALID Windows-1252: We face a real-world train unit assignment problem for an operator running trains in a regional area. Given a set of timetabled train trips, each with a required number of passenger seats, and a set of train units, each with a given number of available seats, the problem calls for an assignment of the train units to trips, possibly combining more than one train unit for a given trip, that fulfills the seat requests. With respect to analogous case studies previously faced in the literature, ours is characterized by the fairly large number of distinct train unit types available (in addition to the fairly large number of trips to be covered). As a result, although there is a wide margin of improvement over the solution used by the practitioners (as our results show), even only finding a solution of the same value is challenging in practice. We present a successful approach, based on an ILP formulation in which the seat requirement constraints are stated in a “strong” form, derived from the description of the convex hull of the variant of the knapsack polytope arising when the sum of the variables is restricted not to exceed two, illustrating computational results on our case study.
Cite as

Valentina Cacchiani, Alberto Caprara, and Paolo Toth. 06. Solving a Real-World Train Unit Assignment Problem. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 79-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{cacchiani_et_al:OASIcs.ATMOS.2007.1172,
  author =	{Cacchiani, Valentina and Caprara, Alberto and Toth, Paolo},
  title =	{{06. Solving a Real-World Train Unit Assignment Problem}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{79--95},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1172},
  URN =		{urn:nbn:de:0030-drops-11726},
  doi =		{10.4230/OASIcs.ATMOS.2007.1172},
  annote =	{Keywords: }
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact